import java.util.ArrayList;
import java.util.List;

public class LeetCode46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<List<Integer>> res) {
        // 如果 start 达到数组长度，说明已经生成了一个完整的排列
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            res.add(permutation);
            return;
        }
        // 从 start 开始，尝试将每个数字放到当前位置
        for (int i = start; i < nums.length; i++) {
            // 交换 nums[start] 和 nums[i]
            swap(nums, start, i);
            // 递归处理下一个位置
            backtrack(nums, start + 1, res);
            // 回溯，恢复原状
            swap(nums, start, i);
        }
    }

    //// 交换数组中的两个元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
